package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-30 14:36
 **/
public class LeetCode1296 {

    public boolean isPossibleDivide(int[] hand, int groupSize) {
        int n = hand.length;

        //如果手牌数量不能整除groupSize,直接返回false
        if (n % groupSize != 0) {
            return false;
        }

        //对手牌进行排序
        Arrays.sort(hand);

        Map<Integer, Integer> map = new HashMap<>();
        //对牌进行计数
        for (int num : hand) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //对手牌进行分组,最小的数为x,则如果存在顺子,该组数字范围为[x, x + groupSize - 1],然后对剩下的牌再次采用同样的方法分组
        for (int num : hand) {
            //如果map中已经不存在num的key,说明该数已经被分组分好了
            if (!map.containsKey(num)) {
                continue;
            }

            for (int i = 0; i < groupSize; i++) {
                int temp = num + i;
                //如果当前组的[num, num + groupSize - 1],范围中有某个数不存在,则直接返回false
                if (!map.containsKey(temp)) {
                    return false;
                }

                //map中temp对应的value--
                map.put(temp, map.get(temp) - 1);
                //如果该数字的value为0,只说明该数字已经分组完毕,直接移出map
                if (map.get(temp) == 0) {
                    map.remove(temp);
                }

            }
        }
        return true;
    }

}
